Codeforces Round 655 Div2 A~D题解

闲话:这场居然因为queueforces unrated了,如果打了的话我应该出的了ABC
本场传送门:https://codeforces.com/contest/1372/

A. Omkar and Completion
题目大意:构造一个长度为nn的数列aa,使之满足任意两个数之和在数列里不存在。
分析:直接构造一个11111..111111111..1111的数列就可以了。

B. Omkar and Last Class of Math
题目大意:给定一个整数nn,找到一组数对(a,b)(a,b)满足a+b=na+b=nlcm(a,b)lcm(a,b)最大。
数据范围:
1T101 \leq T \leq 10
2n1092 \leq n \leq 10^9
分析:首先有两个变量,先消个元看一下:原式lcm(a,na)lcm(a,n - a),由于lcmlcm不怎么熟悉,就换成比较熟悉的gcdgcd再看:原式=a(na)gcd(a,na)\dfrac{a * (n - a)}{gcd(a,n - a)},发现下面这个gcdgcd满足差分形式,即gcd(a,na)=gcd(a,n)gcd(a,n - a) = gcd(a,n),由于要使原式最大,故可以猜测一个结论:aa的取值是nn的最大约数,找出nn的最小质因子ppnp\frac{n}{p}就是最大的约数了。
不过到此实际上还没解决问题(会WA4),因为如果数nn是个质数,那么他压根就没有任何的质因子,所以还需要特殊处理一下。由于nn是一个质数,则任何小于nn的数aa与之互质,即gcd(n,a)=1gcd(n,a)=1,故原式=a(na)a * (n - a),答案显然是当a=1a=1是最小,输出即可。
代码:

using namespace std;
typedef long long ll;
const int N = 1e5+7;
int primes[N],cnt,st[N];
void init()
{
	for(int i = 2;i < N;++i)
	{
		if(!st[i])	primes[++cnt] = i;
		for(int j = 1;j <= cnt && i * primes[j] < N;++j)
		{
			st[i * primes[j]] = 1;
			if(i % primes[j] == 0)	break;
		}
	}
}
int main()
{
	init();
    int T;scanf("%d",&T);
    while(T--)
    {
		int n;scanf("%d",&n);
    	int ok = 0;
    	for(int i = 1;i <= cnt;++i)
    	{
    		if(n % primes[i] == 0)
    		{
    			printf("%d %d\n",n / primes[i],n - n / primes[i]);
    			ok = 1;
    			break;
    		}
    	}
    	if(!ok)
    	{
    		printf("%d %d\n",1,n - 1);
    	}
    }
    return 0;
}

C. Omkar and Baseball
题目大意:给定一个长度为nn的数列{a}\{a\},且{a}\{a\}是一组排列数,现在规定一种操作:每次可以选取一个区间,把区间内的数随意换位置,如果换完之后每个位置上的数都与原来的数不同,则可以进行这个操作,把新的数全换上去,否则不可以执行。问最少要几次可以完成对原数列的排序。
数据范围:
1n21051 \leq n \leq 2*10^5
分析:首先由于数据范围很大,所以说最多也就遍历一次。手玩几组数据之后,一个大概的想法就是:开头和结尾已经有序的部分,肯定不用管了,所以要管的就是中间的部分。而中间这个部分可以分成两种情况:一种是中间有没有出现一个已经是有序的数,和中间完全是乱序的。
先看后面一种,我们可以发现如果中间完全是乱序的,只需要11次操作就可以解决问题了。
如果是前者,中间出现了一个有序的数,这时只需要额外再操作11次就可以解决问题了,第一步先把所有的其他数排好,之前有序的跟身边的一个交换一下位置,第二次把上次有序的和他旁边那个数再交换一下。
至此可以发现这个题的答案只有三种:0,1,20,1,2,贪心策略是正确的。直接去遍历一遍查中间是不是有已经有序的就行了。
代码:

using namespace std;
typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n;scanf("%d",&n);
		vector<int> a(n + 17),st(n + 17);
		for(int i = 1;i <= n;++i)	scanf("%d",&a[i]);
		int flag = 0,last = -1;
		for(int i = 1;i <= n;++i)
		{
			if(a[i] != i)
			{
				if(flag == 0)	flag = 1,last = i;
				else if(flag == 1)
				{
					if(last == -1)	last = i;
					else if(last != i - 1)	flag = 2;
					
					if(flag != 2)	last = i;
				}
				// cout << flag << " " << last << endl;
			}
		}
		printf("%d\n",flag);
    }
    return 0;
}

D. Omkar and Circle
题目大意:给定一个长度为nnnn是奇数的数列{a}\{a\},这个数列呈环状。每次可以选择环上的一个数,把这个数和他相邻的两个数删掉,用他相邻的两个数代替他。问最后整个环能得到的最大值是多少。
数据范围:
1n21051 \leq n \leq 2 *10^5
0ai1090 \leq a_i \leq 10^9
注意答案爆intint

分析:首先nn的范围太大了,常规区间dp不可取。我们必须要有一个线性的做法。分析之后可以发现这个题最大的困难在于某个点ii的值更新依赖于两边,而两边的贡献难算且很可能超复杂度,所以这个题必须要先做一步转换,看能不能消掉这个问题。
进而我们可以发现这个题是包装过的:用旁边两个数代替他,等价于把他自己删去,然后剩下的所有的数的和就是答案。形式化的语言来说明这个题目就是:在环上删掉n2\frac{n}{2}个不相邻的数,使最后剩下来的和最大。由于本题是一个环,所以我们先要想怎么拆环变数列:复制环成两倍是可以的,不过还有另外一种:先把a1a_1ana_n看做是断开的,就是他俩不能相连的情况算出第一个答案,那么还剩下一种情况:他俩相连应该是什么样的,这个问题之后再分析,因为他涉及到实际的题目情况,不过想到这里的时候基本可以敲定正确性了,往下做没什么问题。
在一个数列上做这个题的时候,如果暴力dpdp枚举有多少个数删去了转移肯定是不行的,还要找到一个可以快速计算出答案得性质:由于说整个数列长度nn是个奇数,从里面扣n2\frac{n}{2}个数之后,会产生n2\frac{n}{2}个空隙,那么一共剩下了n2+1\frac{n}{2} + 1个数,故一定有两个没有被删的数是相邻的,并且只有一个。于是我们可以枚举所有可能情况:即枚举所有位置ii,表示相邻的那两个数的右端点的下标是ii,然后发现如果我们根据奇偶性来做前缀和的话,这个信息是非常好统计的,就可以以O(1)O(1)的代价算出删去的数的和了。于是复杂度就成功降到了O(n)O(n)
现在我们回过头来看一下之前的那个问题:缺少的第二个条件该怎么补充。缺少的那个情况就是a1a_1ana_n没有相邻的情况,于是可以把ana_n挪到a1a_1的前面,再做一次答案的求解过程,就可以把这种情况加上了。
分析完了具体该怎么分类之后,说明一下这个题该怎么实现。
首先这道题其实是一个原题(到这里来的话),题目是atcoder的abc_162F题,链接:https://atcoder.jp/contests/abc162/tasks/abc162_f
定义f[x]f[x]为开始到xx依次选不相邻的数时的总和。
入口:f[1]=a[1]f[1] = a[1],其余为0
递推:f[i]=f[i2]+a[i]f[i] = f[i - 2] + a[i]
注意这个前缀和是隔了一位的,推式子的时候要注意其实际意义。
如果当前枚举的ii是个奇数的话,答案是:f[n1]f[i1]+f[i2]f[n - 1] - f[i - 1] + f[i - 2]

如果当前枚举的ii是个偶数的话,答案是:f[i2]+f[n]f[i1]f[i - 2] + f[n] - f[i - 1]

最后,不要忘了做出另外一个数组bb,再做一次。
当然,实际上bb数组可以不用做满所有的操作,具体情况可以自己思考一下。
代码:

using namespace std;
typedef long long ll;
const int N = 2e5+7,INF = 1e9+7;
int a[N],b[N];
int n;
ll f[N];
ll slove(int c[])
{
	f[1] = c[1];
	// for(int i = 1;i <= n;++i)	cout << c[i] << " ";cout << endl;
	for(int i = 2;i <= n;++i)	f[i] = f[i - 2] + c[i];
	ll res = 1e18;
	for(int i = 2;i <= n;++i)
	{
		if(i % 2 == 0)
		{
			res = min(res,f[i - 2] + f[n] - f[i - 1]);
		}
		else
		{
			res = min(res,f[n - 1] - f[i - 1] + f[i - 2]);
		}
	}
	return res;
}
int main()
{
	scanf("%d",&n);
	ll sum = 0;
	for(int i = 1;i <= n;++i)	scanf("%d",&a[i]),sum += a[i];
	if(n == 1)
	{
		printf("%d",a[1]);
		return 0;
	}
	ll res = 0;
	res = max(res,sum - slove(a));
	b[1] = a[n];
	for(int i = 2;i <= n;++i)	b[i] = a[i - 1];
	// for(int i = 1;i <= n;++i)	cout << b[i] << " ";cout << endl;
	res = max(res,sum - slove(b));
	printf("%lld",res);
    return 0;
}